Methods, apparatus, and systems for efficient partitioning and construction of graphs for scalable high-performance search applications. A method for partitioning a set of ternary keys having one or more wildcards includes analyzing patterns of the set of ternary keys and storing ternary keys with the same pattern in the same subset. The patterns may include uncompressed patterns and compressed patterns. When there are more patterns than a target number of subgraphs, patterns are repeatedly merged until the number of merged patterns matches the target number of subgraphs. Table entries having ternary keys corresponding to the ternary keys in a final set of merged patterns of ternary keys are generated and partitioned into sub-tables, with each sub-table associated with a respective sub-graph. Tables with hundreds of thousands or millions of entries are supported.