Dong Xin
Jiawei Han
ABSTRACT
The family of threshold algorithm (ie, TA) has been widely studied for efficiently computing top-k queries. TA uses a sort-merge framework that assumes data lists are pre-sorted, and the ranking functions are monotone. However, in many database applications, attribute values are indexed by tree-structured indices (eg, B-tree, R-tree), and the ranking functions are not necessarily monotone. To answer top-k queries with ad-hoc ranking functions, this paper studies anindex-merge paradigm that performs progressive search over the space of joint states composed by multiple index nodes.
We address two challenges for efficient query processing. First, to minimize the search complexity, we present a double-heap algorithm which supports not only progressive state search but also progressive state generation. Second, to avoid unnecessary disk access, we characterize a type of "empty-state" that does not contribute to the final results, and propose a new materialization model, join-signature, to prune empty-states. Our performance study shows that the proposed method achieves one order of magnitude speed-up over baseline solutions.
- H. Bast, D. Majumdar, R. Schenkel, M. Theobald, and G. Weikum. Io-top-k: Index-access optimized top-k query processing. In VLDB, pages 475--486, 2006. Google Scholar
Digital Library
- K. Beyer and R. Ramakrishnan. Bottom-up computation of sparse and iceberg cubes. In SIGMOD Conference, pages 359--370, 1999. Google ScholarDigital Library
- B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422--426, 1970. Google ScholarDigital Library
- C. Bohm and H. P. Kriegel. Determining the convex hull in large multidimensional databases. In DaWaK, pages 294--306. Springer-Verlag, 2001.Google Scholar
- S. Borzsonyi, D. Kossmann, and K. Stocker. The skyline operator. In ICDE, pages 421--430, 2001. Google ScholarDigital Library
- T. Brinkhoff, H. P. Kriegel, and B. Seeger. Efficient processing of spatial joins using r-trees. In SIGMOD Conference, pages 237--246, 1993. Google ScholarDigital Library
- N. Bruno, L. Gravano, and A. Marian. Evaluating top-k queries over web-accessible databases. In ICDE, 2002.Google ScholarCross Ref
- K. Chakrabarti, V. Ganti, J. Han, and D. Xin. Ranking objects by exploiting relationships: computing top-k over aggregation. In SIGMOD Conference, pages 371--382, 2006. Google ScholarDigital Library
- S. Churdhuri and U. Dayal. An overview of data warehousing and data cube. SIGMOD Record, 26:65--74, 1997. Google ScholarDigital Library
- R. Fagin. Fuzzy queries in multimedia database systems. In PODS, pages 1--10, 1998. Google ScholarDigital Library
- R. Fagin. Combining fuzzy information: an overview. SIGMOD Record, 31(2):109--118, 2002. Google ScholarDigital Library
- R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In PODS, 2001. Google ScholarDigital Library
- A. Fraenkel and S. Klein. Novel compression of sparse bit-strings-preliminary report. Combinatorial Algorithms on Words, NATO ASI Series, 12:169--183, 1985.Google Scholar
- H. Garcia-Molina, J. D. Ullman, and J. Widom. Database Systems: The Complete Book. Prentice Hall, 2002. Google ScholarDigital Library
- G. R. Hjaltason and H. Samet. Incremental distance join algorithms for spatial databases. In SIGMOD Conference, pages 237--248, 1998. Google ScholarDigital Library
- S. Michel, P. Triantafillou, and G. Weikum. Klee: a framework for distributed top-k query algorithms. In VLDB, pages 637--648, 2005. Google ScholarDigital Library
- K. Morfonios and Y. Ioannidis. Cure for cubes: cubing using a rolap engine. In VLDB, pages 379--390, 2006. Google ScholarDigital Library
- D. Papadias, Y. Tao, G. Fu, and B. Seeger. Progressive skyline computation in database systems. ACM Trans. Database Syst., 30(1):41--82, 2005. Google ScholarDigital Library
- H. Shin, B. Moon, and S. Lee. Adaptive and incremental processing for distance join queries. IEEE Trans. Knowl. Data Eng., 15(6):1561--1578, 2003. Google ScholarDigital Library
- P. Valduriez. Join indices. ACM Trans. Database Systems, 12:218--246, 1987. Google ScholarDigital Library
- D. Xin, J. Han, H. Cheng, and X. Li. Answering top-k queries with multi-dimensional selections: The ranking cube approach. In VLDB, pages 463--475, 2006. Google ScholarDigital Library
- Z. Zhang, S. won Hwang, K. C. C. Chang, M. Wang, C. A. Lang, and Y. C. Chang. Boolean + ranking: querying a database by k-constrained optimization. In SIGMOD Conference, pages 359--370, 2006. Google ScholarDigital Library
- M. Zhu, D. Papadias, J. Zhang, and D. L. Lee. Top-k spatial joins. IEEE Trans. Knowl. Data Eng., 17(4):567--579, 2005. Google ScholarDigital Library
Index Terms
- Progressive and selective merge: computing top-k with ad-hoc ranking functions
Recommendations
Top-k best probability queries and semantics ranking properties on probabilistic databases
There has been much interest in answering top-k queries on probabilistic data in various applications such as market analysis, personalized services, and decision making. In probabilistic relational databases, the most common problem in answering top-k ...
Monochromatic and Bichromatic Reverse Top-k Queries
Nowadays, most applications return to the user a limited set of ranked results based on the individual user's preferences, which are commonly expressed through top-k queries. From the perspective of a manufacturer, it is imperative that her products ...
Scalable top-k keyword search in relational databases
DASFAA'12: Proceedings of the 17th international conference on Database Systems for Advanced Applications - Volume Part IIKeyword search in relational databases has been widely studied in recent years because it does not require users neither to master a certain structured query language nor to know the complex underlying database schemas. There would be a huge number of ...
Comments