## 3 Learned Semantic Index Structure
### SPARQL Join Query Algorithms for Learned Semantic Index  
SPARQL is a standard query language for the RDF data model. As SPARQL statements can be represented as graphs, we transform SPARQL into a query graph to perform query processing. There are two types of SPARQL queries--single and join triple pattern queries. Processing queries with a single triple pattern is straightforward. When a query consists of multiple triple patterns that share at least one variable, we call it a join triple pattern query. In SPARQL queries, there are eight triple patterns: (?s,?p,?o), (s, p, o), (s, p, o), (s, p, o), (s, p, o), (s,?p, o), (?s,?p, o), and (?s, p,?o). SPARQL queries can be divided into seven different join types [27]: star (only subject-subject join), chain (only subject-object join), directed cycle (only subject-object), tree (subject-subject and subject-object), cycle (subject-subject and subject-object), single (only subject or object), and complex (random combination). The nearest neighbor (NN) algorithm finds the nearest vectors to a given query pattern; this is also called similarity or proximity search. Applying this algorithm to high  
Figure 3: Overall architecture of the learned semantic index structure. dimensional spaces deteriorates performance because the distance between NNs can be large. Thus, much research has focused on finding approximations of the exact NNs. In this study, an approximate NN algorithm is presented to find \(k\) approximate nearest vectors in embedding space to a query pattern by using \(k\)-d tree. We can measure the similarity between each triple vector and a query vector through vector similarity (e.g., cosine similarity and Euclidean distance). Several experiments demonstrated that the Euclidean distance similarity provides excellent accuracy. Therefore, we adopt the Euclidean distance between two vectors in embedding space as the measure of relevance. Let a vectorized triple \(v\) and query \(q\) have coordinates (\(v_{1}\),..., \(v_{n}\)) and (\(q_{1}\),..., \(q_{n}\)), respectively, in \(n\)-dimensional embedded space, then the distance \(d(v,q)\) between \(v\) and \(q\) is given by:  
\[d(v,q)=\sqrt{\sum_{i=1}^{n}(v_{i}-q_{i})^{2}} \tag{4}\]  
In this study, the density-based spatial clustering of applications with noise (DBSCAN) model was adopted to cluster similar semantic vectors. The DBSCAN model is a well-known, unsupervised machine learning tool for clustering [28]. The DBSCAN creates clusters based on dense regions while marking points that lie alone in low-density regions as outliers. In DBSCAN, the density is detected via core points that are quite sensitive to input parameters: \(\varepsilon\) is the radius of the neighborhood, and _minPts_ is the minimum number of points constrained within \(\varepsilon\) radius. To ensure that all vectors cluster without noise vectors, minimum samples are set to 1. There are two key points for complex join queries: join ordering and selecting the most suitable join algorithm [29]. Algorithm 1 shows a detailed illustration of our SPARQL join query algorithm for semantic search. In the process of a query pattern, different join algorithms--hash join, nested loop join, and sort-merge join--are combined to replace the traditional single join query algorithm, because, in the actual experiments, we found that the use of different join algorithms has a certain impact on the actual join query performance. For example, when we want to perform a join calculation on results of two subqueries A and B, using the nested loop join algorithm is suitable if the data volume of A and B is relatively small. However, using the hash join algorithm has better performance if the query result of A is very large. The most suitable query type for hash join is the star query. However, a serious weakness of the simple hash join is the poor performance for complex non-star queries. We propose a hybrid join search algorithm that combines the hash join for star and the nested loop join for non-star queries.