Database Reference
In-Depth Information
3.2.1 Distributed Top-k Query Processing
Distributed top-
k
query processing focuses on reducing communication cost while
providing high quality answers. [65] studies top-
k
monitoring queries which con-
tinuously report the
k
largest values from data streams produced at physically dis-
tributed locations. In [65], there are multiple logical data objects and each object
is associated with an overall logical data value. Updates to overall logical data val-
ues arrive incrementally over time from distributed locations. Efficient techniques
are proposed to compute and maintain the top-
k
logical data objects over time with
low communication cost among distributed locations and a bounded error tolerance.
In [66], an algorithmic framework is proposed to process distributed top-
k
queries,
where the index lists of attribute values are distributed across a number of data peers.
The framework provides high quality approximation answers and reduces network
communication cost, local peer load, and query response time.
3.3 Top-
k
Typicality Queries
Aside from the studies reviewed in Sections 3.1 and 3.2, the top-
k
typicality queries
that will be discussed in Chapter 4 is also related to the previous work in the follow-
ing aspects: typicality in psychology and cognitive science, the
k
-median problem,
typicality probability and spatially-decaying aggregation.
3.3.1 Typicality in Psychology and Cognitive Science
Typicality of objects has been widely discussed in psychology and cognitive sci-
ence [67, 68]. People judge some objects to be “better examples” of a concept than
others. This is known as the
graded structure
[69] of a category. Generally, the
graded structure is a continuum of category representativeness, beginning with the
most typical members of a category and continuing through less typical members to
its atypical members.
There are several determinants of graded structure. One determinant is the
central
tendency
[70] of a category. Central tendency is either one or several very represen-
tative exemplar(s), either existing in the category or not. An exemplar's similarities
to the central tendency determine its typicality in this category. Another determinant
of typicality is the
stimulus similarity
[71]. Generally, the more similar an instance
is to the other members of its category, and the less similar it is to members of the
contrast categories, the higher the typicality rating it has.
The prototype view [72] suggests that a concept be represented by a prototype,
such that objects “closer to” or “more similar to” the prototype are considered to
be better examples of the associated concept. The exemplar view [73] is an alterna-
tive to the prototype view that proposes using real objects as exemplars instead of
