Article

Scalable ranking for preference queries

Authors:

Ying Feng,

Divyakant Agrawal,

Amr El Abbadi,

Ambuj SinghAuthors Info & Claims

CIKM '05: Proceedings of the 14th ACM international conference on Information and knowledge management

Pages 313 - 314

https://doi.org/10.1145/1099554.1099643

Published: 31 October 2005 Publication History

Get Access

Abstract

Top-k preference queries with multiple attributes are critical for decision-making applications. Previous research has concentrated on improving the computational efficiency mainly by using novel index structures and search strategies. Since current applications need to scale to terabytes of data and thousands of users, performance of such systems is strongly impacted by the amount of available memory. This paper proposes a scalable approach for memory-bounded top-k query processing.

References

[1]

J. L. Bentley. Multidimensional divider-and-conquer. Communications of the ACM, pages 214--229, 1980.

Digital Library

Google Scholar

[2]

N. Bruno, S. Chaudhuri, and L. Gravano. Top-k selection queries over relational databases: Mapping strategies and performance evaluation. ACM TODS, 27(2):153--187, 2002.

Digital Library

Google Scholar

[3]

Y. Chang, L. Bergman, V. Castelli, C. Li, M. L. Lo, and J. Smith. The onion technique: Indexing for linear optimization queries. In SIGMOD, pages 391--402, 2000.

Digital Library

Google Scholar

[4]

R. Fagin. Fuzzy queries in multimedia database systems. In PODS, pages 1--10, 1998.

Digital Library

Google Scholar

[5]

R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In PODS, 2001.

Digital Library

Google Scholar

[6]

Y. Feng, D. Agrawal, A. E. Abbadi, and A. Singh. Scalable and optimal ranking for preference queries. Technical report, UCSB, 2005.

Google Scholar

[7]

U. Guntzer, W. Balke, and W. Kiebling. Optimizing mulit-feature queries for image database. In VLDB, 2000.

Digital Library

Google Scholar

[8]

G. Hjaltason and H. Samet. Ranking in spatial databases. In SSD, pages 83--95, 1995.

Digital Library

Google Scholar

[9]

P. Tsaparas, T. Palpanas, Y. Kotidis, N. Koudas, and D. Srivastava. Ranked join indices. In ICDE, 2003.

Crossref

Google Scholar

Index Terms

Scalable ranking for preference queries
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Semantic optimization techniques for preference queries

Preference queries are relational algebra or SQL queries that contain occurrences of the winnow operator (find the most preferred tuples in a given relation). Such queries are parameterized by specific preference relations. Semantic optimization ...
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database Theory

The problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...
MiniCon: A scalable algorithm for answering queries using views

The problem of answering queries using views is to find efficient methods of answering a query using a set of previously materialized views over the database, rather than accessing the database relations. The problem has received significant attention ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CIKM '05: Proceedings of the 14th ACM international conference on Information and knowledge management

October 2005

854 pages

ISBN:1595931406

DOI:10.1145/1099554

General Chair:
Otthein Herzog
University of Bremen, Germany
,
Program Chairs:
Hans-Jörg Schek
University for Health Sciences, Medical Informatics and Technology, Austria
,
Norbert Fuhr
University of Duisburg-Essen, Germany
,
Abdur Chowdhury
America Online, USA
,
Wilfried Teiken
IBM T.J. Watson Research Center, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 October 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM05

Sponsor:

CIKM05: Conference on Information and Knowledge Management

October 31 - November 5, 2005

Bremen, Germany

Acceptance Rates

CIKM '05 Paper Acceptance Rate 77 of 425 submissions, 18%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
284
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Index Terms

Recommendations

Semantic optimization techniques for preference queries

Equivalence and minimization of conjunctive queries under combined semantics

MiniCon: A scalable algorithm for answering queries using views