QOSI
QOSI - Quadrillion Open Source Indexer

QOSI - Quadrillion Open Source Indexer


Glossary
Basic Descriptors
Object
Definition: Any unit that can be processed or analyzed by the QOSI system.
Types:
File, File ID,
Offset, Offset Index
Tokenized File, Tokenized File ID
Candidate Object List, Candidate Object Bitmap
MTS, MTSU
Bitmap
TODO:
etc.
Target
Definition: User-provided objects intended for analysis.
Descriptions:
Consists of objects submitted by the user.
Always remains separate and is never merged into the Source.
Characteristics:
Relatively smaller than the Source.
Never incorporated into the Source.
Workflow:
Is subject to immediate tokenization and/or indexing once received.
Source
Definition: Objects to match against the Target.
Description:
Objects maintained by the service provider.
The main data collection (objects) for queries and comparisons.
Characteristics:
Acts as the reference pool for matching against the Target.
Mainly OSS(Open Source Software) or other public datasets.
It is readily available. Pre-indexed.
It is updated infrequently
e.g., weekly or monthly
TODO: Move to Indexing
Candidate Indexing duration has no significant impact on data structure design.
Candidate
Definition: Potential objects with common subsequence with the Target.
Description:
Identified during the Candidate Query phase.
Subset of the Source.
Characteristics:
May include false positives but never false negatives.
Used to quickly identify potential matches in the Source.
In current, every candidate includes MTS, but may not include MSs.
Identified
Definition: The subset of Source/Target objects that contain a common subsequence with Target/Source.
Description:
Identified during the Comparing phase.
Identified Source: Source objects that contain a common subsequence with the Target.
Identified Target: Target objects that contain a common subsequence with the Source.
Index
Definition: A metadata to identify the order of the data. Similar to ID.
Description:
Many objects (ex: File, Tokenized File, Token, etc.) have their own Index.
Immutable
Definition: Would not be changed during the process.
Description:
The Index is immutable after the indexing phase(when the index is created).
Dataset
Dataset
Definition: An aggregated collection of objects.
Characteristics:
Each Dataset may contain numerous objects
A dataset may contain only the same type or different types of objects.
source code, text, etc.
File, Tokenized File, Candidate Object List
Source Dataset
Definition: The comprehensive set of objects maintained as the Source.
Usage:
Interchangeably referred to simply as "Source."
Target Dataset
Definition: The complete set of objects the user provides.
Usage:
Interchangeably referred to simply as "Target."
Token and Sequence
Token
Definition: The smallest unit of data derived from the content of a file.
Description:
Generated through tokenization—splitting code or text into discrete elements.
Varies by language; e.g., whitespace-based for Western languages, morphological analysis for Japanese.
Characteristics:
Enables fine-grained comparison between Source and Target files.
Significantly reduces duplication compared to entire lines or blocks of text.
Details:
Code Data: Tokenized according to code syntax rules.
Text Data (Natural Language):
Western Languages: Split by spaces (plus punctuation considerations).
Chinese: Every character is treated as a token.
Korean: Split by spaces; postpositional particles and suffixes are separately tokenized.
Japanese: Uses morphological analysis to segment words based on grammar and context.
Special Cases: Korean/Japanese require specialized tokenizers due to morphological complexity.
Syntax Token
Definition: A token that does not reflect its original string but its syntax role.
String Token
Definition: A token that reflects its original string.
Sequence and Subsequence
Definition:
Sequence: An ordered list of tokens derived from a file or segment.
Subsequence: A contiguous subset of tokens within a sequence.
Description:
Used for matching and comparison processes (e.g., detecting shared code fragments).
Minimum Token Sequence (MTS) and Minimum Token Sequence Unit (MTSU)
Definition:
MTS: A fixed-size subsequence of tokens from the original sequence.
MTSU: The hashed version of an MTS, serving as a fundamental unit for indexing, candidating, and comparing.
Characteristics:
MTSU is generated by hashing an MTS.
Because an MTS is multiple tokens combined, it reduces the chance of random duplication compared to single-token matching.
Minimum Subsequence (MSs) (or Minimum Token Subsequence (MTSs))
Definition: The subsequence that is requested by minimum size(length) by the user.
Details:
MSs should be equal or greater(longer) than MTS.
When comparing on Comparator, connect MTS(MTSU) to construct MSs.
Example:
MTS: 3 tokens
MSs: 5 tokens
When finding a MSs 
A B C D E in a file, the Comparator will find MTS 
A B C, 
B C D and 
C D E by MTSU and match it to MSs 
A B C D E.
Hash Function
Definition: A function that converts an MTS into a fixed-size value (an MTSU).
Description:
Ensures consistent, quick comparisons.
Takes not only a Token, but Token Subsequence to get more identification power.
File and Tokenized File
File
Definition: A code and/or text container.
Description:
Consists of a sequence of original tokens (raw source code, natural language text).
Only Reporter(viewer) access the file directly
In Indexing, and Comparing phases, the system uses Tokenized Files.
Characteristics:
Typically stored in a filesystem or code repository.
Source Files are stored in Archiver.
Can be part of either Source Dataset or a Target Dataset.
Tokenized File
Definition: A file after it has been converted into a sequence of tokens.
Description:
Produced by a tokenizer from the raw file.
Consists of pairs: 
(**Token Index**, **MTSU**, separated token #1, separated token #2, ...).
Token Index
Definition: The token's position in the token sequence of the file.
Partitioning
Definition: Dividing something by MTSU to optimize searching.
Candidate Index, File Archive, and etc.
Query
Query, Query Request, and Query Result
Definition:
Query: The act of searching the Source for common subsequences found in the Target.
Query Request: Specific search parameters used to locate relevant subsequences in Source files.
Query Result: The outcome of a Query, typically pairing Target files with matching Source files.
Description:
Involves scanning across the entire Target dataset to find potential matches in the Source.
Candidate Queries help identify which Source files might contain matching subsequences.
Types:
Exact Query: Finds subsequences that match exactly between Source and Target.
Similar Query: Finds similar subsequences, given a user-defined similarity threshold.
Result:
Pairs each Source file with the relevant Target file.
Includes index ranges (start/end) of matching subsequences for both files.
By Token Index
By Line Number
Candidate Query
Definition:** A preliminary, broad search returns only a list of candidate files from the Source.
Description:
Operates over the entire Source dataset.
Allows false positives but no false negatives (i.e., it might over-include but never miss a true match).
It does not directly support similar queries (though smaller MTS sizes can approximate similarity).
Batch Query
Definition: A method for processing multiple queries to improve efficiency.
Characteristics:
Reduces repeated work by handling similar queries in a single pass.
Constructed by MTS list
Link between Source ID and MTS is not sent to Nominator, but stored in Querier.
Example:
Target Object A's Token Sequence: 
A B C D E F G
A's MTS:
A B C
B C D
C D E
D E F
E F G
Target Object B's Token Sequence: 
A B C E F G
B's MTS:
A B C
B C E
C E F
E F G
Batch Query: 
A B C, 
B C D, 
C D E, 
B C E, 
C E F, 
E F G
Common MSss among Target Object (ex: 
A B C, 
E F G)are not duplicated in Batch Query
Preprocess Phase
Preprocessor
Definition: A component that converts a File to a Tokenized File, and extract metadata.
Description:
Extracts metadata from the file.
Include Tokenizing(Tokenizer)
Tokenizer
Definition: A component that converts a File to a sequence of tokens and make a Tokenized File.
File Archiver
Definition: Retrieves a Source File and/or Source Tokenized File’s content by the file ID.
Description:
Archive Source Files and Source Tokenized Files, and its metadata.
Index Phase
Candidate Index (The Index)
Definition: A data structure built from candidate Source files to facilitate queries.
Description:
Used to respond to Candidate Queries quickly.
It acts as a high-level map of Source Files.
Is immutable after the indexing phase.
Nominator does not modify The Index.
Is organized (sorted) by MTSU to speed up lookups.
Partitioning is applied to The Index for efficient searching.
Types:
Raw Candidate Index
Is not optimized or compressed.
May use RocksDB or LevelDB.
Candidate Index, The Index
Is optimized and compressed.
Nominator uses this index.
Indexer (Source File Indexer)
Definition: Builds the Index from the Source datasets.
Description:
Converts Source Files into Tokenized Files.
Generates MTSU entries and relevant metadata for the Index.
Workflow
From Tokenized File, record the file ID by MTSU to Candidate Index.
Index Compressor
Definition: Extract Key-Value and Compress to reduce the size of the Index to improve performance.
Description:
Workflow:
Extract Key-Value pairs from Candidate Index.
Compress Key-Value pairs by Elias-Fano Encoding.
Query Phase
Querier
Definition: Generates and executes queries based on Target Files.
Description:
Before Querier, it should pass Preprocessing for Target.
Produces Query Requests that lists MTSU and metadata from the Target Object.
Generate Batch Query
May group or deduplicate MTSU to optimize further searching.
Stores MTSU and Source ID map.
Nominator
Definition: Identifies candidate files during query operations.
Description:
Takes a Query Request and looks up possible file matches from the Index.
Returns a list of Source file IDs that contain matching MTSU.
Key: MTSU
Value: Source file ID list (by Bitmap)
Comparison Phase
Merger
Definition: Consolidates and refines the final list of candidate files after a candidate query from Nominator.
Description:
Produces the final candidate file set for the Query.
Combines results across multiple MTSU lookups for each Target File.
Use Bitmap to merge(OR operation) the candidate file list.
File Extractor
Comparator
Evaluator
Reporter
Partitioning
Language Family
Definition: A grouping of languages based on similar syntax or representation.
Description:
Languages in the same family may share identical tokenization patterns.
A single language can belong to multiple families if it exhibits shared features with different groups.
Helps partition Source data for more efficient indexing and searching.
Parameter
Parameter
Definition: A user-defined setting that customizes query behavior.
Types:
Similarity Rate: Sets the degree of overlap needed for matches in a Similar Query.
Search Unit (by token):
MTSU Size: The smallest hashable subsequence size.
Minimum Search Unit Size: The smallest token sequence considered for matching.
Description:
Affects how queries are performed and how results are filtered.
Allows for tuning accuracy versus performance.