1998 · 342 citations · 13 references
ComputingComputer ScienceAlgorithmsData MiningInformation RetrievalBasket AnalysisData WarehousingHash TablesQuery ProcessingSearching AlgorithmsWeb MiningAggregate FunctionsAggregate Query ProcessingAggregation ProcessingCopy DetectionHashing
Many applications compute aggregate functions over an attribute (or set of attributes) to find aggregate values above some specified threshold. We call such queries iceberg queries, because the number of abovethreshold results is often very small (the tip of an iceberg), relative to the large amount of input data (the iceberg). Such iceberg queries are common in many applications, including data warehousing, information-retrieval, market basket analysis in data mining, clustering and copy detection. We propose efficient algorithms to evaluate iceberg queries using very little memory and significantly fewer passes over data, when compared to current techniques that use sorting or hashing. We present an experimental case study using over three gigabytes of Web data to illustrate the savings obtained by our algorithms. 1 Introduction In this paper we develop efficient execution strategies for an important class of queries that we call iceberg queries. An iceberg query performs an aggre...
13
Principles of database and knowledge-base systems
Choice Reviews Online · 1989 · 2.7K citations
Dynamic itemset counting and implication rules for market basket data
Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman et al. · 1997 · 2K citations
On the resemblance and containment of documents
Arndt Bröder · 2002 · 1.7K citations