The Experts below are selected from a list of 309 Experts worldwide ranked by ideXlab platform
Rakesh Agrawal - One of the best experts on this subject based on the ideXlab platform.
-
high Dimensional Similarity joins
IEEE Transactions on Knowledge and Data Engineering, 2002Co-Authors: Kyuseok Shim, Ramakrishnan Srikant, Rakesh AgrawalAbstract:Many emerging data mining applications require a Similarity join between points in a high-Dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsi/ tree, for fast spatial Similarity joins on high-Dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence, the proposed index structure scales to high-Dimensional data. We analyze the cost of the join for the /spl epsi/ tree and the R-tree family, and show that the /spl epsi/ tree will perform better for high-Dimensional joins. Empirical evaluation, using synthetic and real-life data sets, shows that Similarity join using the /spl epsi/ tree is twice to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions. We also discuss how some of the ideas of the /spl epsi/ tree can be applied to the R-tree family. These biased R-trees perform better than the corresponding traditional R-trees for high-Dimensional Similarity joins, but do not match the performance of the /spl epsi/ tree.
-
high Dimensional Similarity joins
International Conference on Data Engineering, 1997Co-Authors: Kyuseok Shim, Ramakrishnan Srikant, Rakesh AgrawalAbstract:Many emerging data mining applications require a Similarity join between points in a high-Dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsiv/-kdB tree, for fast spatial Similarity joins on high-Dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence the proposed index structure scales to high-Dimensional data. Empirical evaluation, using synthetic and real-life datasets, shows that Similarity join using the /spl epsiv/-kdB tree is 2 to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions.
-
ICDE - High-Dimensional Similarity joins
Proceedings 13th International Conference on Data Engineering, 1997Co-Authors: Kyuseok Shim, Ramakrishnan Srikant, Rakesh AgrawalAbstract:Many emerging data mining applications require a Similarity join between points in a high-Dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsiv/-kdB tree, for fast spatial Similarity joins on high-Dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence the proposed index structure scales to high-Dimensional data. Empirical evaluation, using synthetic and real-life datasets, shows that Similarity join using the /spl epsiv/-kdB tree is 2 to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions.
Guadalupe Canahuate - One of the best experts on this subject based on the ideXlab platform.
-
High-Dimensional Similarity searches using query driven dynamic quantization and distributed indexing
Distributed and Parallel Databases, 2019Co-Authors: Gheorghi Guzun, Guadalupe CanahuateAbstract:The concept of Similarity is used as the basis for many data exploration and data mining tasks. Nearest neighbor (NN) queries identify the most similar items, or in terms of distance the closest points to a query point. Similarity is traditionally characterized using a distance function between multi-Dimensional feature vectors. However, when the data is high-Dimensional, traditional distance functions fail to significantly distinguish between the closest and furthest points, as few dissimilar dimensions dominate the distance function. Localized Similarity functions, i.e. functions that only consider dimensions close to the query, quantize each dimension independently and only compute Similarity for the dimensions where the query and the points fall into the same bin. These quantizations are query-agnostic and there is potential to improve accuracy when a query-dependent quantization is used. In this work we propose a query dependent equi-depth (QED) on-the-fly quantization method to improve high-Dimensional Similarity searches. The quantization is done for each dimension at query time and localized scores are generated for the closest p fraction of the points while a constant penalty is applied for the rest of the points. QED not only improves the quality of the distance metric, but also improves query time performance by filtering out non relevant data. We propose a distributed indexing and query algorithm to efficiently compute QED. Our experimental results show improvements in classification accuracy as well as query performance up to one order of magnitude faster than Manhattan-based sequential scan NN queries over datasets with hundreds of dimensions. Furthermore, Similarity searches with QED show linear or better scalability in relation to the number of dimensions, and the number of compute nodes.
-
distributed query aware quantization for high Dimensional Similarity searches
Extending Database Technology, 2018Co-Authors: Gheorghi Guzun, Guadalupe CanahuateAbstract:The concept of Similarity is used as the basis for many data exploration and data mining tasks. Nearest Neighbor (NN) queries identify the most similar items, or in terms of distance the closest points to a query point. Similarity is traditionally characterized using a distance function between multi-Dimensional feature vectors. However, when the data is high-Dimensional, traditional distance functions fail to significantly distinguish between the closest and furthest points, as few dissimilar dimensions dominate the distance function. Localized Similarity functions, i.e. functions that only consider dimensions close to the query, quantize each dimension independently and only compute Similarity for the dimensions where the query and the points fall into the same bin. These quantizations are query-agnostic. There is potential to improve accuracy when a query-dependent quantization is used. In this paper we propose a Query dependent Equi-Depth (QED) on-the-fly quantization method to improve high-Dimensional Similarity searches. The quantization is done for each dimension at query time and localized scores are generated for the closest p fraction of the points while a constant penalty is applied for the rest of the points. QED not only improves the quality of the distance metric, but also improves query time performance by filtering out non relevant data. We propose a distributed indexing and query algorithm to efficiently compute QED. Our experimental results show improvements in classification accuracy as well as query performance up to one order of magnitude faster than Manhattan-based sequential scan NN queries over datasets with hundreds of dimensions.
-
EDBT - Distributed query-aware quantization for high-Dimensional Similarity searches
2018Co-Authors: Gheorghi Guzun, Guadalupe CanahuateAbstract:The concept of Similarity is used as the basis for many data exploration and data mining tasks. Nearest Neighbor (NN) queries identify the most similar items, or in terms of distance the closest points to a query point. Similarity is traditionally characterized using a distance function between multi-Dimensional feature vectors. However, when the data is high-Dimensional, traditional distance functions fail to significantly distinguish between the closest and furthest points, as few dissimilar dimensions dominate the distance function. Localized Similarity functions, i.e. functions that only consider dimensions close to the query, quantize each dimension independently and only compute Similarity for the dimensions where the query and the points fall into the same bin. These quantizations are query-agnostic. There is potential to improve accuracy when a query-dependent quantization is used. In this paper we propose a Query dependent Equi-Depth (QED) on-the-fly quantization method to improve high-Dimensional Similarity searches. The quantization is done for each dimension at query time and localized scores are generated for the closest p fraction of the points while a constant penalty is applied for the rest of the points. QED not only improves the quality of the distance metric, but also improves query time performance by filtering out non relevant data. We propose a distributed indexing and query algorithm to efficiently compute QED. Our experimental results show improvements in classification accuracy as well as query performance up to one order of magnitude faster than Manhattan-based sequential scan NN queries over datasets with hundreds of dimensions.
Kyuseok Shim - One of the best experts on this subject based on the ideXlab platform.
-
high Dimensional Similarity joins
IEEE Transactions on Knowledge and Data Engineering, 2002Co-Authors: Kyuseok Shim, Ramakrishnan Srikant, Rakesh AgrawalAbstract:Many emerging data mining applications require a Similarity join between points in a high-Dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsi/ tree, for fast spatial Similarity joins on high-Dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence, the proposed index structure scales to high-Dimensional data. We analyze the cost of the join for the /spl epsi/ tree and the R-tree family, and show that the /spl epsi/ tree will perform better for high-Dimensional joins. Empirical evaluation, using synthetic and real-life data sets, shows that Similarity join using the /spl epsi/ tree is twice to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions. We also discuss how some of the ideas of the /spl epsi/ tree can be applied to the R-tree family. These biased R-trees perform better than the corresponding traditional R-trees for high-Dimensional Similarity joins, but do not match the performance of the /spl epsi/ tree.
-
high Dimensional Similarity joins
International Conference on Data Engineering, 1997Co-Authors: Kyuseok Shim, Ramakrishnan Srikant, Rakesh AgrawalAbstract:Many emerging data mining applications require a Similarity join between points in a high-Dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsiv/-kdB tree, for fast spatial Similarity joins on high-Dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence the proposed index structure scales to high-Dimensional data. Empirical evaluation, using synthetic and real-life datasets, shows that Similarity join using the /spl epsiv/-kdB tree is 2 to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions.
-
ICDE - High-Dimensional Similarity joins
Proceedings 13th International Conference on Data Engineering, 1997Co-Authors: Kyuseok Shim, Ramakrishnan Srikant, Rakesh AgrawalAbstract:Many emerging data mining applications require a Similarity join between points in a high-Dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsiv/-kdB tree, for fast spatial Similarity joins on high-Dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence the proposed index structure scales to high-Dimensional data. Empirical evaluation, using synthetic and real-life datasets, shows that Similarity join using the /spl epsiv/-kdB tree is 2 to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions.
Kenneth C Sevcik - One of the best experts on this subject based on the ideXlab platform.
-
high Dimensional Similarity joins algorithms and performance evaluation
IEEE Transactions on Knowledge and Data Engineering, 2000Co-Authors: Nick Koudas, Kenneth C SevcikAbstract:Current data repositories include a variety of data types, including audio, images, and time series. State-of-the-art techniques for indexing such data and doing query processing rely on a transformation of data elements into points in a multiDimensional feature space. Indexing and query processing then take place in the feature space. We study algorithms for finding relationships among points in multiDimensional feature spaces, specifically algorithms for multiDimensional joins. Like joins of conventional relations, correlations between multiDimensional feature spaces can offer valuable information about the data sets involved. We present several algorithmic paradigms for solving the multiDimensional join problem and we discuss their features and limitations. We propose a generalization of the size separation spatial join algorithm, named multiDimensional spatial join (MSJ), to solve the multiDimensional join problem. We evaluate MSJ along with several other specific algorithms, comparing their performance for various Dimensionalities on both real and synthetic multiDimensional data sets. Our experimental results indicate that MSJ, which is based on space filling curves, consistently yields good performance across a wide range of Dimensionalities.
-
ICDE - High Dimensional Similarity joins: algorithms and performance evaluation
Proceedings 14th International Conference on Data Engineering, 1998Co-Authors: Nick Koudas, Kenneth C SevcikAbstract:Current data repositories include a variety of data types, including audio, images and time series. State of the art techniques for indexing such data and doing query processing rely on a transformation of data elements into points in a multiDimensional feature space. Indexing and query processing then take place in the feature space. We study algorithms for finding relationships among points in multiDimensional feature spaces, specifically algorithms for multiDimensional joins. Like joins of conventional relations, correlations between multiDimensional feature spaces can offer valuable information about the data sets involved. We present several algorithmic paradigms for solving the multiDimensional join problem, and we discuss their features and limitations. We propose a generalization of the Size Separation Spatial Join algorithm, named MultiDimensional Spatial Join (MSJ), to solve the multiDimensional join problem. We evaluate MSJ along with several other specific algorithms, comparing their performance for various Dimensionalities on both real and synthetic multiDimensional data sets. Our experimental results indicate that MSJ, which is based on space filling curves, consistently yields good performance across a wide range of Dimensionalities.
Ramakrishnan Srikant - One of the best experts on this subject based on the ideXlab platform.
-
high Dimensional Similarity joins
IEEE Transactions on Knowledge and Data Engineering, 2002Co-Authors: Kyuseok Shim, Ramakrishnan Srikant, Rakesh AgrawalAbstract:Many emerging data mining applications require a Similarity join between points in a high-Dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsi/ tree, for fast spatial Similarity joins on high-Dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence, the proposed index structure scales to high-Dimensional data. We analyze the cost of the join for the /spl epsi/ tree and the R-tree family, and show that the /spl epsi/ tree will perform better for high-Dimensional joins. Empirical evaluation, using synthetic and real-life data sets, shows that Similarity join using the /spl epsi/ tree is twice to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions. We also discuss how some of the ideas of the /spl epsi/ tree can be applied to the R-tree family. These biased R-trees perform better than the corresponding traditional R-trees for high-Dimensional Similarity joins, but do not match the performance of the /spl epsi/ tree.
-
high Dimensional Similarity joins
International Conference on Data Engineering, 1997Co-Authors: Kyuseok Shim, Ramakrishnan Srikant, Rakesh AgrawalAbstract:Many emerging data mining applications require a Similarity join between points in a high-Dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsiv/-kdB tree, for fast spatial Similarity joins on high-Dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence the proposed index structure scales to high-Dimensional data. Empirical evaluation, using synthetic and real-life datasets, shows that Similarity join using the /spl epsiv/-kdB tree is 2 to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions.
-
ICDE - High-Dimensional Similarity joins
Proceedings 13th International Conference on Data Engineering, 1997Co-Authors: Kyuseok Shim, Ramakrishnan Srikant, Rakesh AgrawalAbstract:Many emerging data mining applications require a Similarity join between points in a high-Dimensional domain. We present a new algorithm that utilizes a new index structure, called the /spl epsiv/-kdB tree, for fast spatial Similarity joins on high-Dimensional points. This index structure reduces the number of neighboring leaf nodes that are considered for the join test, as well as the traversal cost of finding appropriate branches in the internal nodes. The storage cost for internal nodes is independent of the number of dimensions. Hence the proposed index structure scales to high-Dimensional data. Empirical evaluation, using synthetic and real-life datasets, shows that Similarity join using the /spl epsiv/-kdB tree is 2 to an order of magnitude faster than the R/sup +/ tree, with the performance gap increasing with the number of dimensions.