Athens University Economics and Business (AUEB)
Similarity computation in modern applications
Abstract
dc:descriptionComputing the similarity between data items is a fundamental operation in data management. The first part of the thesis proposes a technique that is utilized in distributed applications for computing the similarity between data descriptions that are streamed from remote sources. The proposed technique utilizes prior knowledge of the data distribution in order to produce, with the same space, more accurate descriptions than the Random Hyperplane Projection (RHP) method (i.e. a locality sensitive hashing method). We present algorithms that materialize RHP dimensions that better describe the underlying data, while additional dimensions are derived in real-time using simple stored statistics we maintain. Our method is resilient to data distribution changes because of a fail-safe mechanism that detects in real time cases where particular data instances cannot be accurately described using the selected dimensions. In such cases the method automatically falls-back into using the basic RHP scheme. The second part of this work introduces a novel user-centric approach for similarity computation between products. Unlike techniques that focus on product features our method takes into account users’ preferences by utilizing the recent concept of reverse top-k queries. In contrast to a top-k query that returns the k products with the best score for a specific customer, the result of a reverse top-k query is the set of customers(or their rankings) for whom a given product belongs to their top-k set. Two novel query types (θ-similarity and m-nearest neighbor) for user-centric similarity search are defined, while algorithms for efficient processing of these queries are also discussed. The presented algorithms prune the search space by identifying effective similarity bounds and exploit conventional multi-dimensional indexes for efficient query processing. In the third part of this thesis we address the problem of outlier detection in hierarchically organized data domains. Outlier detection is critical for modern applications such as decision support (OLAP) and network management. However, existing techniques do not take into consideration the hierarchical nature of the data domains that is inherent in such applications. The natural aggregation of atomic values along a domain hierarchy is an intuitive summarization technique that can be used to detect diferent grades of abnormal behavior by looking across all levels of the hierarchy. In this work, we first formally define the notion of a hierarchical outlier and describe an intuitive monotonicity property that permits us to rate an outlier with a single grade value. We then present a technique that combines locality sensitive hashing and clustering in order to index the data descriptions. The fusion of both techniques permits us to reduce the storage space for the index and the execution time for an outlier computation query.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2017
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Georgoulas, Konstantinos
- Γεωργούλας, Κωνσταντίνος
Subjects
dc:subject × 6Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/41418