STARS

This code is the implementation of our research paper "STARS: A Sampling and Threshold Sharing Solution for Network K-function Analytics". Based on our theoretical analysis in this paper, this method can further reduce the time complexity for generating Network K-function plot.

Due to space limitations in this Github link, we do not upload the datasets. However, since all datasets are open to public, readers can simply download these datasets from the source webpages. To call our code properly, readers need to process these datasets based on our input file structure, which is shown in the file "file_structure.txt".

Code Descriptions

The file "sam_count.cpp" shows the implementation of the method STARS. For implementation details of the threshold sharing mechanism used in STARS (Section 3.2), please refer to:

👉 docs/threshold_sharing.md

Quick Start

1. Clone Repository

$ git clone https://github.com/yeswin411/STARS.git
$ cd STARS

2. Build with CMake (Recommended)

$ mkdir build && cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ make -j4

3. Run Example

./STARS data/example_network ./example_output 7 5 5 2 2 0.1

Alternative Compilation

For direct compilation without CMake:

g++ ./src/*.cpp -O3 -o STARS

Data format

See file_structure.txt for specifications and example dataset for a concrete example.

Usage

Parameter Specification

./STARS DATASET_DIR RESULT_DIR METHOD L D START_TAU INCR_TAU [SAMPLING_THRESHOLD]

Parameter	Type	Description	Constraints
DATASET_DIR	Path	Input dataset directory	Must follow file structure
RESULT_DIR	Path	Output file path	Directory must exist
METHOD	Integer [1-8]	Algorithm selection	See method table
L	Integer ≥1	Total datasets (1 real + L-1 randomly generated)
D	Integer ≥1	Number of distance thresholds
START_TAU	Float	Initial threshold	>0
INCR_TAU	Float	Threshold increment	>0
SAMPLING_THRESHOLD	Float [0-1]	Sampling rate (Methods 7/8)

Method Taxonomy

Code	Method	Description
1	RQS	Range-Query-based Solution
2	SPS	Shortest Path Sharing
3	CA	Count Augmentation
4	NS	Neighbor Sharing
5	CA(ASPS)	Advanced SPS with CA
6	NS(ASPS)	Advanced SPS with NS
7	STARS	Proposed Method (Threshold Sharing + Sampling)
8	SAMPLING+NS	NS with sampling

Example Configurations

STARS Method

./STARS data/Chicago result/chicago_stars 7 5 20 100 100 0.1

Baseline Method (RQS)

./STARS data/Chicago result/chicago_rqs 1 5 20 100 100 0.0