A time optimized scheme for top-k list maintenance over incomplete data streams

Abstract

A large number of contemporary research efforts focus on incomplete data streams handling. These efforts, usually, focus on the creation and maintenance of top-k lists useful to provide efficient responses to top-k queries. In case of large volumes of data accumulated at high rates the problem becomes more intense as an efficient method for maintaining the top-k list is considered imperative. In this paper, we focus on the behavior of an Observer Entity (OE) responsible to observe the incoming data and initiate the maintenance process of the top-k list. The maintenance process involves the calculation of a score for each object and the update of the top-k list. We adopt the principles of Optimal Stopping Theory (OST) and introduce a scheme that determines, in the appropriate time, when the OE decides to initiate the maintenance process. Due to the incomplete data setting, the high rate of the incoming data and the large volume of data, the maintenance process is initiated only when the OE has the appropriate amount of information for providing a top-k list. In contrast to other research approaches, we do not maintain any additional sets of objects. Instead, we attempt to minimize the number of the necessary processing tasks over the list of objects. We present a mathematical analysis for our scheme and an extensive experimental evaluation. The comparison with other models shows that the proposed model provides efficiency in the list management and minimizes the required time to result the final top-k list. (c) 2015 Elsevier Inc. All rights reserved.