Abstract

The query programs of certain databases report raw statistics for query sets, which are groups of records specified implicitly by a characteristic formula. The raw statistics include query set size and sums of powers of values in the query set. Many users and designers believe that the individual records will remain confidential as long as query programs refuse to report the statistics of query sets which are too small. It is shown that the compromise of small query sets can in fact almost always be accomplished with the help of characteristic formulas called trackers. Schlörer's individual tracker is reviewed; it is derived from known characteristics of a given individual and permits deducing additional characteristics he may have. The general tracker is introduced: It permits calculating statistics for arbitrary query sets, without requiring preknowledge of anything in the database. General trackers always exist if there are enough distinguishable classes of individuals in the database, in which case the trackers have a simple form. Almost all databases have a general tracker, and general trackers are almost always easy to find. Security is not guaranteed by the lack of a general tracker.

Keywords

Computer scienceBitTorrent trackerSet (abstract data type)Information retrievalQuery optimizationOnline aggregationSargableViewDatabaseWeb query classificationSimple (philosophy)Query languageData miningWeb search querySearch engineDatabase designArtificial intelligenceEye tracking

Affiliated Institutions

Related Publications

Publication Info

Year
1979
Type
article
Volume
4
Issue
1
Pages
76-96
Citations
206
Access
Closed

External Links

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

206
OpenAlex

Cite This

Dorothy E. Denning, Peter J. Denning, Mayer D. Schwartz (1979). The tracker. ACM Transactions on Database Systems , 4 (1) , 76-96. https://doi.org/10.1145/320064.320069

Identifiers

DOI
10.1145/320064.320069